Logique combinatoire

Pour les articles homonymes, voir combinatoire (homonymie).

Cet article traite de la logique combinatoire, au sens qu'a ce mot en logique mathématique et en informatique théorique. Il ne doit pas être confondu avec ce que l'on appelle logique combinatoire en électronique.

En logique mathématique, la logique combinatoire est une théorie logique^[1] introduite par Moses Schönfinkel^[2] en 1920 lors d'une conférence^{[Laquelle ?]} et développée dès 1929 par Haskell Brooks Curry^[3] pour supprimer le besoin de variables en mathématiques, pour formaliser rigoureusement la notion de fonction et pour minimiser le nombre d'opérateurs nécessaires pour définir le calcul des prédicats à la suite de Henry M. Sheffer. Plus récemment, elle a été utilisée en informatique comme modèle théorique de calcul et comme base pour la conception de langages de programmation fonctionnels.

Le concept de base de la logique combinatoire est celui de combinateur qui est une fonction d'ordre supérieur ; elle utilise uniquement l'application de fonctions et éventuellement d'autres combinateurs pour définir de nouvelles fonctions d'ordre supérieur. Chaque combinateur simplement typable est une démonstration à la Hilbert en logique intuitionniste et vice-versa ^[4]. On appelle ceci la correspondance de Curry-Howard